package myArrayList;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/9 19:26
 *  实现顺序表：物理上元素相邻的线性表
 *  
 *  约束：
 *     0<= size <= array.length
 *     array[0,size) !=null
 *     array[size , array.length) ==null
 */
public class MyArrayList implements MyList{
    //定义属性
    private Long[] array;  //array.length 也就是容量capacity
    private int size;  //保存元素个数
    //构造方法
    public MyArrayList(){
        //容量没规定 自定义16
        this.array=new Long[16];
        //初始化为 null
        for (int i = 0; i < array.length; i++) {
            array[i]=null;
        }
        //元素个数 0
        this.size = 0;
    }
    
    public MyArrayList(int initialCapacity){
        //容量没规定 自定义initialCapacity
        this.array=new Long[initialCapacity];
        //初始化为 null
        for (int i = 0; i < array.length; i++) {
            array[i]=null;
        }
        //元素个数 0
        this.size = 0;
    }
    @Override
    public int size() {
        return size;
    }
    // 扩容过程仅仅为了内部准备，不会对外
    // O(n)
    private void ensureCapacity() {
        if (this.size < this.array.length) {
            return;     // 此时不需要扩容
        }

        // 需要扩容
        // 1) 申请新数组，容量是原来的 2 倍
        int newLength = this.array.length * 2;
        Long[] newArray = new Long[newLength];

        // 2) 搬家
        for (int i = 0; i < this.size; i++) {
            newArray[i] = this.array[i];
        }

        // 3) 让顺序表的 array 引用指向新数组
        this.array = newArray;
    }

    // 时间复杂度：数据规模是 size，时间复杂度是 O(1)
    // 最坏情况，发生扩容的情况： O(n)
    // 我们认为扩容的发生是小概率事件
    // 平均事件复杂度：O(1)
    @Override
    public boolean add(Long e) {
        ensureCapacity();   // 这个方法结束之后，至少还有一个空间可以插入

        //size 就是 尾插元素的位置
        array[size] = e;
        //元素加1
        size++;
        //尾插成功
        return true;
    }

    @Override
    public void add(int index, Long e) {
        ensureCapacity();   // 这个方法结束之后，至少还有一个空间可以插入

        if(index<0||index>size){
            //下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }
        //此处下标一定合法
        for (int i = size-1; i >=index ; i--) {
            array[i+1]=array[i];
        }
        //赋值
        array[index]=e;
        //size+1
        size++;
    }

    @Override
    public Long remove(int index) {
        if(index<0||index>=size){
            //下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }
        long ret = array[index];
        for (int i = index+1; i < size; i++) {
            array[i-1]=array[i];
        }
        array[size-1]=null;
        size--;

        return ret;
    }

    @Override
    public boolean remove(Long e) {
        for (int i = 0; i < size; i++) {
            if(array[i].equals(e)){
                remove(i);
                return  true;
            }
        }
        return false;
    }

    // O(1)
    @Override
    public Long get(int index) {// 下标合法性检查
        if (index < 0 || index >= size) {
            // 下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }

        return array[index];
    }

    // O(1)
    @Override
    public Long set(int index, Long e) {
        // 下标合法性检查
        if (index < 0 || index >= size) {
            // 下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }

        Long oldE = array[index];

        array[index] = e;

        return oldE;
    }


    // O(n)
    @Override
    public int indexOf(Long e) {
        for (int i = 0; i < size; i++) {
            if (array[i].equals(e)) {
                return i;
            }
        }

        return -1;
    }

    // O(n)
    @Override
    public int lastIndexOf(Long e) {
        for (int i = size - 1; i >= 0; i--) {
            if (array[i].equals(e)) {
                return i;
            }
        }

        return -1;
    }
    // O(n)
    @Override
    public boolean contains(Long e) {
        return indexOf(e) != -1;
    }
    @Override
    public void clear() {
        // array 中全部置为 null
        for (int i = 0; i < size; i++) {
            array[i] = null;
        }
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private static void 检查顺序表是否合法(MyArrayList myArrayList){
        //0<=size<= arr.length
        if (myArrayList.size<0){
            throw new RuntimeException();
        }
        if(myArrayList.size> myArrayList.array.length){
            throw new RuntimeException();
        }
        //array[0,size) != null
        for (int i = 0; i < myArrayList.size() ; i++) {
            if(myArrayList.array[i]==null){
                throw new RuntimeException();
            }
        }
        //array[size,arr.length) == null
        for (int i = myArrayList.size; i < myArrayList.array.length; i++) {
            if(myArrayList.array[i]!=null){
                throw new RuntimeException();
            }
        }
    }

    private static void 断言顺序表的元素个数一定是(MyArrayList list, int size) {
        if (list.size != size) {
            throw new RuntimeException();
        }
    }

    private static void 断言顺序表的指定位置元素一定是(MyArrayList list, int index, long e) {
        // Long != long
        // long != long
        if (list.array[index] != e) {
            throw new RuntimeException();
        }
    }

    public static void main(String[] args) {
      // 之所以把测试代码写这里，是方便读取 private 的属性
        MyArrayList myArrayList = new MyArrayList();
        //无参构造的顺序表 ，size 为 0
        if(myArrayList.size!=0){
            throw new RuntimeException();
        }

        // 先测试尾插 add()
        boolean r;
        r = myArrayList.add(Long.valueOf(100));
        // 检查 r 必须是 true
        if (r == false) {
            throw new RuntimeException();
        }
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 1);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 100);

        //add 200
        r = myArrayList.add(200L);         // 编译器自动把 long 包装成 Long
        if (r == false) {
            throw new RuntimeException();
        }
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 2);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 200);

        //add 300
        r = myArrayList.add(300L);         // 编译器自动把 long 包装成 Long
        if (r == false) {
            throw new RuntimeException();
        }
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 3);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 300);

        // 测试 根据 index 进行插入 add(int index, Long e)

        // [100, 200, 300]
        myArrayList.add(3, 1000L);
        // [100, 200, 300, 1000]
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 4);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 1000);

        // [100, 200, 300, 1000]
        myArrayList.add(0, 2000L);
        // [2000, 100, 200, 300, 1000]
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 5);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 1000);

        // [2000, 100, 200, 300, 1000]
        myArrayList.add(2, 3000L);
        // [2000, 100, 3000, 200, 300, 1000]
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 6);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 3000);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 5, 1000);

        // [2000, 100, 3000, 200, 300, 1000]
//        list.add(13, 4000L);    // 非法下标，应该看到 下标越界异常

        // [2000, 100, 3000, 200, 300, 1000]
        Long e = myArrayList.remove(2);
        // [2000, 100, 200, 300, 1000]
        if (e != 3000) {
            throw new RuntimeException();
        }
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 5);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 1000);

        // 同学自己测试下删除 remove(0)  remove(size - 1)
        // [2000, 100, 200, 300, 1000]
        e = myArrayList.remove(0);
        if (e != 2000) {
            throw new RuntimeException();
        }
        // [100, 200, 300, 1000]
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 4);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 1000);
        // [100, 200, 300, 1000]
        e = myArrayList.remove(myArrayList.size-1);
        if (e != 1000) {
            throw new RuntimeException();
        }
        // [100, 200, 300]
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 3);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 300);
        //还原
        myArrayList.add(0,2000L);
        myArrayList.add(myArrayList.size, 1000L);
        //检测
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 5);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 100);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 1000);
        // [2000, 100, 200, 300, 1000]
        r = myArrayList.remove(100L);
        // [2000, 200, 300, 1000]
        if (r == false) {
            throw new RuntimeException();
        }

        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 4);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 1000);


        // [2000, 200, 300, 1000]
        myArrayList.add(200L);
        myArrayList.add(200L);
        // [2000, 200, 300, 1000, 200, 200]
        r = myArrayList.remove(200L);
        // [2000, 300, 1000, 200, 200]
        if (r == false) {
            throw new RuntimeException();
        }

        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 5);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 1000);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 200);

        // 同学测试，如果没有元素 r = remove(5000L);
        // [2000, 300, 1000, 200, 200]
        r = myArrayList.remove(5000L); //false
        if (r != false) {
            throw new RuntimeException();
        }

        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 5);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 1000);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 200);

        myArrayList.add(5000L);
        myArrayList.add(6000L);
        myArrayList.add(5000L);
        // [2000, 300, 1000, 200, 200, 5000, 6000, 5000]
        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 8);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 1000);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 5, 5000);
        断言顺序表的指定位置元素一定是(myArrayList, 6, 6000);
        断言顺序表的指定位置元素一定是(myArrayList, 7, 5000);

        // [2000, 300, 1000, 200, 200, 5000, 6000, 5000]
        r = myArrayList.remove(5000L); //ture
        // [2000, 300, 1000, 200, 200, 6000, 5000]
        if (r == false) {
            throw new RuntimeException();
        }

        检查顺序表是否合法(myArrayList);
        断言顺序表的元素个数一定是(myArrayList, 7);
        断言顺序表的指定位置元素一定是(myArrayList, 0, 2000);
        断言顺序表的指定位置元素一定是(myArrayList, 1, 300);
        断言顺序表的指定位置元素一定是(myArrayList, 2, 1000);
        断言顺序表的指定位置元素一定是(myArrayList, 3, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 4, 200);
        断言顺序表的指定位置元素一定是(myArrayList, 5, 6000);
        断言顺序表的指定位置元素一定是(myArrayList, 6, 5000);

    }
}
